//
// Description: 52. N皇后II
// Created by Loading on 2021/1/24.
//


#include <bits/stdc++.h>

using namespace std;

int Backtracking(vector<int> &queens, unordered_set<int> &cols, unordered_set<int> &diagonals1,
                 unordered_set<int> &diagonals2,
                 int n,
                 int row) {
    if (row == n) {//一轮遍历结束，计数
        return 1;
    } else {
        int count = 0;
        for (int i = 0; i < n; ++i) {
            if (cols.find(i) != cols.end()) {//此列存在皇后
                continue;
            }
            int dia1 = row + i;
            if (diagonals1.find(dia1) != diagonals1.end()) {//左对角线存在皇后
                continue;
            }
            int dia2 = row - i;
            if (diagonals2.find(dia2) != diagonals2.end()) {//右对角线存在皇后
                continue;
            }
            queens[row] = i;//满足条件，放置皇后
            cols.insert(i);
            diagonals1.insert(dia1);
            diagonals2.insert(dia2);
            count += Backtracking(queens, cols, diagonals1, diagonals2, n, row + 1);//递归，向后寻找
            //递归完毕，重置标记
            queens[row] = -1;
            cols.erase(i);
            diagonals1.erase(dia1);
            diagonals2.erase(dia2);
        }
        return count;
    }
}

int totalNQueens(int n) {
    vector<int> queens(n, -1);

    //列，两侧对角线 标记
    unordered_set<int> cols;
    unordered_set<int> diagonals1;
    unordered_set<int> diagonals2;
    //回溯算法
    return Backtracking(queens, cols, diagonals1, diagonals2, n, 0);
}

int main() {
    int n = 9;//皇后数量

    cout << n << "个皇后的解决方案数为：" << totalNQueens(n) << endl;
}